package main.Q1_100;

import java.util.*;

public class Q71_80 {
    public static void main(String[] args) {
        System.out.println("Question71：简化路径");
        System.out.println("Question72：编辑距离");
        System.out.println("Question73：矩阵置零");
        System.out.println("Question74：搜索二维矩阵");
        System.out.println("Question75：颜色分类");
        System.out.println("Question76：最小覆盖子串");
        System.out.println("Question77：组合");
        System.out.println("Question78：子集");
        System.out.println("Question79：单词搜索");
        System.out.println("Question80：删除有序数组中的重复项Ⅱ");
    }
}

class Question71{
    public String simplifyPath(String path) {
        String result="";
        String[] splits = path.split("/");
        Deque<String> deque=new LinkedList<>();
        for (String s:splits) {
            if (s.equals("")||s.equals(".")) {
                continue;
            }else if (s.equals("..")) {
                deque.pollLast();
            }else {
                deque.offerLast(s);
            }
        }
        if (deque.isEmpty()) {
            result="/";
        }else {
            while (!deque.isEmpty()) {
                result=result+"/"+deque.pollFirst();
            }
        }
        return result;
    }
}

class Question72{
    public int minDistance(String word1, String word2) {
        int length1=word1.length(),length2=word2.length();
        int[][] dp=new int[length1+1][length2+1];
        char[] str1=word1.toCharArray(),str2=word2.toCharArray();
        for (int i=0;i<=length2;i++) dp[0][i]=i;
        for (int i=0;i<=length1;i++) dp[i][0]=i;
        for (int i=1;i<=length1;i++){
            for (int j=1;j<=length2;j++){
                int min=1;
                if (str1[i-1]!=str2[j-1]) min+=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
                else min=dp[i-1][j-1];
                dp[i][j]=min;
            }
        }
        return dp[length1][length2];
    }
}

class Question73{
    public void setZeroes(int[][] matrix) {
        List<Integer> col=new ArrayList<>();//记录列
        List<Integer> row=new ArrayList<>();//记录行
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++)
                if (matrix[i][j]==0) {
                    row.add(i);//将原本为0的位置记录
                    col.add(j);
                }
        }
        for (int i=0;i<row.size();i++){
            int index=row.get(i);
            for (int j=0;j<matrix[0].length;j++) matrix[index][j]=0;//改变行
            index=col.get(i);
            for (int j=0;j< matrix.length;j++) matrix[j][index]=0;//改变列
        }
    }
}

class Question74{
    public boolean searchMatrix(int[][] matrix, int target) {
        int row=-1;
        for (int i=0;i< matrix.length;i++){//确定行
            if (matrix[i][0]<=target) row=i;
        }
        if (row!=-1){
            for (int i=0;i<matrix[0].length;i++){
                if (matrix[row][i]==target) return true;
            }
        }
        return false;
    }
}

class Question75{
    public void sortColors(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
    }
}

class Question76{
    public boolean process(int[] curCount,int[] targetCount){
        for (int i=0;i< targetCount.length;i++){
            if (targetCount[i]!=0&&curCount[i]<targetCount[i]) return false;//目标字符数不足
        }
        return true;
    }
    public String minWindow(String s, String t) {
        int left=0,right=0,start=-1,minLength=Integer.MAX_VALUE;
        if (t.length()>s.length()) return "";
        int[] targetCount=new int[150],curCount=new int[150];
        char[] str=s.toCharArray();
        for (char c:t.toCharArray()) targetCount[c]++;
        while (right< str.length){
            curCount[str[right]]++;//右扩
            while (process(curCount,targetCount)&&left<=right){//左缩
                if (right-left+1<minLength){//满足更新
                    start=left;
                    minLength=right-left+1;
                }
                curCount[str[left]]--;
                left++;
            }
            right++;
        }
        if (start==-1) return "";
        else return s.substring(start,start+minLength);
    }
}

class Question77{
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public void process(int n,int k,int startIndex){
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            process(n, k, i + 1);
            path.removeLast();
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        process(n, k, 1);
        return result;
    }
}

class Question78{
    List<List<Integer>> list=new ArrayList<>();
    public void process(int[] nums,int start,List<Integer> curList){
        if (start>= nums.length){
            list.add(curList);
            return;
        }
        List<Integer> tempList=new ArrayList<>(curList);
        tempList.add(nums[start]);
        list.add(tempList);
        for (int i=start+1;i< nums.length;i++){
            process(nums,i,tempList);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> tempList=new ArrayList<>();
        list.add(tempList);
        for (int i=0;i< nums.length;i++){//以i开始的所有子集
            process(nums,i,tempList);
        }
        return list;
    }
}

class Question79{
    public boolean process(char[][] board,int r,int c,int i,char[] words){
        if (i== words.length-1) return true;
        char[][] temp=process1(board);
        temp[r][c]='#';//标记已经使用过
        boolean up=false,down=false,right=false,left=false;
        int row=board.length,col=board[0].length;
        if (r-1>=0&&temp[r-1][c]==words[i+1]){//上
            up=process(temp,r-1,c,i+1,words);
        }
        if (r+1<row&&temp[r+1][c]==words[i+1]){
            down=process(temp,r+1,c,i+1,words);
        }
        if (c-1>=0&&temp[r][c-1]==words[i+1]){
            left=process(temp,r,c-1,i+1,words);
        }
        if (c+1<col&&temp[r][c+1]==words[i+1]){
            right=process(temp,r,c+1,i+1,words);
        }
        return up||down||right||left;
    }
    public char[][] process1(char[][] board){
        int row= board.length,col=board[0].length;
        char[][] result=new char[row][col];
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++)
                result[i][j]=board[i][j];
        }
        return result;
    }
    public boolean exist(char[][] board, String word) {
        char[] words=word.toCharArray();
        int row= board.length,col=board[0].length;
        for (int i=0;i< board.length;i++){
            for (int j=0;j<board[0].length;j++){
                if (board[i][j]==words[0]){
                    char[][] temp=process1(board);
                    if (process(temp,i,j,0,words)) return true;
                }
            }
        }
        return false;
    }
}

class Question80{
    public int removeDuplicates(int[] nums) {
        int length= nums.length;
        if (length<=2) return length;
        int i=2,j=2;
        while (j<length){
            if (nums[i-2]!=nums[j]){
                nums[i]=nums[j];
                i++;
            }
            j++;
        }
        return i;
    }
}